package 代码记录.剑指offer错题本.hard;

/**
 * @author zx
 * @create 2022-06-23 21:38
 */
public class 正则表达式匹配_19 {
    /**
     * @return 宫水三叶题解
     * 如果最后一个字符是*它代表[c*]可以重复0次或多次,看作一个整体[c∗]
     */
    public boolean isMatch(String s, String p) {
        // 技巧：往原字符头部插入空格,这样得到char数组是从1开始,可以使得f[0][0] = true,将true这个结果滚动下去
        int n = s.length(), m = p.length();
        s = " " + s;
        p = " " + p;
        char[] c1 = s.toCharArray();
        char[] c2 = p.toCharArray();
        //f(i,j)代表考虑s中的1 ~ i字符和p中的1 ~ j字符是否匹配
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果下一个字符是 '*',则代表当前字符不能被单独使用,跳过
                if (j + 1 <= m && c2[j + 1] == '*') {
                    continue;
                }
                // 对应了p[j]为普通字符和 '.' 的两种情况
                if (i - 1 >= 0 && c2[j] != '*') {
                    dp[i][j] = dp[i - 1][j - 1] && (c1[i] == c2[j] || c2[j] == '.');
                }
                // 对应了p[j] 为 '*' 的情况
                else if (c2[j] == '*') {
                    dp[i][j] = (j - 2 >= 0 && dp[i][j - 2]) || (i - 1 >= 0 && dp[i - 1][j] && (c1[i] == c2[j - 1] || c2[j - 1] == '.'));
                }
            }
        }
        return dp[n][m];
    }
}
